题面

解题思路

枚举+贪心

分析

这个也不是很显然，$n\times m$ 的矩形，则 $ans \in [min(n,m),n+m]$，并且 $n$ 或 $m$ 肯定会完整地做出贡献

我们可以把这个模型抽象为有两个长度分别为 $n$ 和 $m$ 的队列，矩形消完的条件便是存在一个队列为空

那么我们现在假设 $n$ 一定能完整地做出贡献，也就是说只要有一行能删，就可以优先删去

因为无论如何，$n$ 可以完整做出贡献，则每行会进行一个删去的操作，先删和后删是等价的（假设我们已经得出删列的最优方案），所以只要贪心选择，能删就删即可

接着再考虑列的删除情况

左或右，删多少，两个变量，对于这种情况，由于列的数目比较小，直接枚举左侧或右侧最多能删去的列数，如此一来就可以贪心地得出另一侧最少需要删多少列，也就可以得出这种情况（一侧确定删去列数）下最少次数

也就是说，我们只需要按照 上下>左>右 的优先级顺序，即可贪心地得出该种情况的最少次数

同理，我们能够处理出 $m$ 能完整做出贡献的情况

在所有情况中取最小即可

Warning

1、枚举一侧删去的行列数时，可能存在不删（即为 $0$ ）的情况，从 $0$ 开始枚举即可

2、注意优先级顺序，以及行列切勿弄混

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 2003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int k,n,m,f[N][N],g[N][N],ans=inf;
inline void solve1(rint val) {
    rint l=1,r=n,i=1,j=m;
    while(i<=j) {
        if(g[r][i]-g[l-1][i]<=k) ++i;//优先左
        else if(g[r][j]-g[l-1][j]<=k) --j;//其次从右侧
        else if(l<=val&&f[l][j]-f[l][i-1]<=k)//在枚举范围内的话从上侧删
            while(l<=val&&f[l][j]-f[l][i-1]<=k) ++l;
        else if(f[r][j]-f[r][i-1]<=k) --r;//否则贪心取下侧
        else return;
    }cmin(ans,n+m-(r-l+1));
}
inline void solve2(rint val) {
    rint l=1,r=m,i=1,j=n;
    while(i<=j) {
        if(f[i][r]-f[i][l-1]<=k) ++i;//优先上
        else if(f[j][r]-f[j][l-1]<=k) --j;//其次下侧
        else if(l<=val&&g[j][l]-g[i-1][l]<=k)//如果允许从左侧
            while(l<=val&&g[j][l]-g[i-1][l]<=k) ++l;
        else if(g[j][r]-g[i-1][r]<=k) --r;//否则贪心右侧
        else return;
    }cmin(ans,n+m-(r-l+1));
}
int main() {
    rint i,j,c;k=read(),m=read(),n=read();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            c=read(),
            f[i][j]=f[i][j-1]+c,//每行的前缀和
            g[i][j]=g[i-1][j]+c;//每列的前缀和
    for(i=0;i<=n;i++) solve1(i);//枚举上侧最多删去行数
    for(j=0;j<=m;j++) solve2(j);//枚举左侧最多删去列数
    printf("%d",ans);
    return 0;
}

devil.